package 我的Java学习_算法基础.day_03;

import java.util.ArrayList;
import java.util.Arrays;

public class _051_基数排序 {
    public static void main(String[] args) {
        int[] a = {5,3,7,2,9,1};
        cardinalSort(a);
        System.out.println(Arrays.toString(a));
    }

    private static ArrayList[] bucket = new ArrayList[10];

    static {
        for (int i = 0; i < bucket.length; i++) {
            bucket[i] = new ArrayList<Integer>();
        }
    }

    public static void cardinalSort(int[] array) {
        int d = 1;  //入桶依据初始化为1
        int max = array[0]; //最大值
        for (int i : array
        ) {
            if (i > max) {
                max = i;
            }
        }
        int dNum = 1;   //最大数据的位数
        while (max / 10 != 0) {
            dNum++;
            max /= 10;
        }
        while (d <= dNum) {
            cardinalSort(array, d++);    //按照第二个参数，依次入桶出桶
        }
    }

    private static void cardinalSort(int[] array, int d) {
        //全部入桶
        for (int i = 0; i < array.length; i++) {
            putInBucket(array[i], getDigitOn(array[i], d));
        }
        //每个桶中的元素，依次压入原数组
        int k = 0;
        for (int j = 0; j < bucket.length; j++) {
            for (Object m : bucket[j]
            ) {
                array[k++] = (Integer) m;
            }
        }
        //清空桶
        clearAll();
    }

    private static void clearAll() {
        //对每个桶调用clear，清空
        for (ArrayList b : bucket
        ) {
            b.clear();
        }
    }

    private static int getDigitOn(int number, int d) {
        int digit = number % 10;
        for (int i = 1; i < d; i++) {
            number /= 10;
            digit = number % 10;
        }
        return digit;
    }

    private static void putInBucket(int current, int digitOn) {
        switch (digitOn) {
            case 0:
                bucket[0].add(current);
                break;
            case 1:
                bucket[1].add(current);
                break;
            case 2:
                bucket[2].add(current);
                break;
            case 3:
                bucket[3].add(current);
                break;
            case 4:
                bucket[4].add(current);
                break;
            case 5:
                bucket[5].add(current);
                break;
            case 6:
                bucket[6].add(current);
                break;
            case 7:
                bucket[7].add(current);
                break;
            case 8:
                bucket[8].add(current);
                break;
            case 9:
                bucket[9].add(current);
                break;
        }
    }

}
